#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

 

示例 1：


输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

TreeNode* insertIntoBST(TreeNode* root, int val) {
    TreeNode* rootRet=root;
    TreeNode* ins=new TreeNode(val);
    if (root== nullptr)
        return ins;
    while (root)
    {
        if (root->val>val)
        {
            if (root->left== nullptr)
            {
                root->left=ins;
                return rootRet;
            }

            root=root->left;

        }

        else{
            if (root->right== nullptr)
            {
                root->right=ins;
                return rootRet;
            }

            root=root->right;
        }


    }




    return rootRet;
}
//递归方式
//返回头节点 TODO 这个写不对 抄的

TreeNode* insertIntoBST(TreeNode* root, int val) {

    if (root== nullptr)
    {
        TreeNode* node = new TreeNode(val);
        //这个写在外面加个sitat 就错了
        return node;
    }

    if (root->val>val)
    {
        root->left=  insertIntoBST(root->left,val);
    } else{

        root->right=  insertIntoBST(root->right,val);
    }


    return root;
}
